package com.example.question.tree.tree2;

import com.example.question.tree.tree1.TreeNode;

/**
 * @Date 2023-07-11
 * @Author Jonathan
 */
public class Code04_236 {


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root, p, q).ancestor;
    }


    private Helper process(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return new Helper(false, false, null);
        }
        Helper left = process(node.left, p, q);
        Helper right = process(node.right, p, q);

        if (left.ancestor != null || right.ancestor != null) {
            return new Helper(true, true, left.ancestor != null ? left.ancestor : right.ancestor);
        }
        // 回溯回来
        // 后序遍历
        boolean containP = left.containP || right.containP || node == p;
        boolean containQ = left.containQ || right.containQ || node == q;

        return new Helper(containP, containQ, containP && containQ ? node : null);
    }


    static class Helper {
        boolean containP;
        boolean containQ;
        TreeNode ancestor;

        public Helper(boolean containP, boolean containQ, TreeNode ancestor) {
            this.containP = containP;
            this.containQ = containQ;
            this.ancestor = ancestor;
        }
    }
}
